import java.util.ArrayDeque;
import java.util.Deque;

public class Day13 {
    // 946、验证栈的序列
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Deque<Integer> stack = new ArrayDeque();
        int i = 0,n = popped.length;
        for(int num : pushed) {
            stack.push(num);
            // 每次放完之后需要和 popped数组第i个位置进行比较，是否是和栈顶数据一致，如果一致，就出栈并i++
            while(!stack.isEmpty() && stack.peek() == popped[i]) {
                stack.pop();
                i++;
            }
        }

        return stack.isEmpty();
    }
}
